package Offer;

/**
 * 把数组排成最小的数
 * 利用快排，创建排序规则为，两个字符串相加，将组合成较小数字的排序方式，将小的放到前边
 * @author 是阿秋啊
 * @date 2022/08/15 21:45
 **/
public class Num45 {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs,0,strs.length - 1);
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }

    private void quickSort(String[] strs, int l, int r) {
        if (l >= r) return;
        int i = l,j = r;
        String tmp = strs[i];
        while (i < j) {
            while (i < j && ((strs[j] + strs[l]).compareTo(strs[l] + strs[j] ) >= 0)) j--;
            while (i < j && ((strs[i] + strs[l]).compareTo(strs[l] + strs[i] ) <= 0)) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        quickSort(strs,l,i - 1);
        quickSort(strs,i + 1,r);
    }
}